Package edu.claflin.finder.logic

Class BronKerboschBipartiteUtils

  • public class BronKerboschBipartiteUtils
extends java.lang.Object
    Provides methods to mark graphs as bipartite using the basic Graph, Edge, and Node classes. Mostly copy-pasted from BipartiteCondition, but modified slightly to be able to mark nodes and return them. To my knowledge the only thing that actually mark nodes uses CytogrouperNode which is a bit different. This class should rectify that.
    Author:
    kpuli007

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static java.util.ArrayList<java.util.ArrayList<Node>> bipartiteDivision​(Graph existingGraph)
      Divides the given graph into bipartite sets.
      static java.util.ArrayList<java.util.ArrayList<Node>> constructArrayList​(java.util.Set<Node> groupA, java.util.Set<Node> groupB)
      Constructs array list of array lists from sets.
      private static boolean satisfies​(Graph existingGraph, java.util.Set<Node> addSet, java.util.Set<Node> compareSet, Node current)
      Private method for stepping through the adjacency lists and determining if the graph is bipartite.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • BronKerboschBipartiteUtils

        public BronKerboschBipartiteUtils()

    • Method Detail

      • bipartiteDivision

        public static java.util.ArrayList<java.util.ArrayList<Node>> bipartiteDivision​(Graph existingGraph)
        Divides the given graph into bipartite sets.
        Returns:
        two lists of nodes, each representing a bipartite group. Both lists are empty if the graph is not a valid bipartite graph.

      • constructArrayList

        public static java.util.ArrayList<java.util.ArrayList<Node>> constructArrayList​(java.util.Set<Node> groupA,
                                                                                java.util.Set<Node> groupB)
        Constructs array list of array lists from sets. Array lists are used over sets to make traversing the graph's nodes (see Graph.addEdgesBetweenAllNodesInList(ArrayList)) possible.
        Parameters:
        groupA - first output set
        groupB - second output set
        Returns:
        array list containing the two sets as array lists

      • satisfies

        private static boolean satisfies​(Graph existingGraph,
                                 java.util.Set<Node> addSet,
                                 java.util.Set<Node> compareSet,
                                 Node current)
        Private method for stepping through the adjacency lists and determining if the graph is bipartite. Specifically, it uses a Depth-First model for exploring the node tree and sorting the nodes into two groups. If it successfully sorts the nodes into two groups with no invalidating edges, it returns true.
        Parameters:
        existingGraph - the Graph object to test against.
        addSet - the current set to add a node to based on the previous.
        compareSet - the current set to add adjacent nodes to.
        current - the current Node being compared.
        Returns:
        true if the structure could be bipartite.